%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Digital Signatures}
\label{DigitalSignatures}

A digital signature is the digital analogue of a handwritten
signature.  The signature of a message is data dependent on some
secret known only to the signer and on the content of the message.
A digital signature must be verifiable without access to the
signer's private key.

\section{RSA Signature Scheme}

The RSA signature scheme is a signature scheme with {\it message
recovery} --- the signed message is recovered from the signature.

\noindent
{\bf Key generation.}  This step is exactly as for RSA enciphering.
The signer generates a public key $(e,n)$ and guards a private key
$(d,n)$, where $n = pq$ is the product of two large primes.

\noindent
{\bf Signature generation.}
Encode the message $m$ in $\Z/n\Z$, and output the signature
$s = m^d \in \Z/n\Z$, computed using the private key $(d,n)$.

\noindent
{\bf Verification.}
Compute $m = s^e \in \Z/n\Z$.

\section{ElGamal Signature Scheme}

The ElGamal signature scheme requires an encoding of the message
$m$ as an element of $\Z/(p-1)\Z$.

\noindent
{\bf Key generation.}  This step is exactly as for ElGamal enciphering.
The signer generates a public key $(p,a,c)$, where $c = a^x \bmod p$,
and guards the private key $(p,a,x)$, where $a$ is a primitive element
of $\Z/p\Z$ and $x$ is an integer in the range $1 \le x < p-1$ with
$\GCD(x,p-1) = 1$.

\noindent
{\bf Signature generation.}
The signer selects a random secret integer $k$ in the range $1\le k<p-1$
with $\GCD(k,p-1)=1$, and computes
$$
r = a^k \bmod p \hbox{ and } s = l (m-rx) \bmod (p-1),
$$
where $l = k^{-1} \bmod (p-1)$, and the signature $(r,s)$ is output.

Note that $r$ is well-defined in $\Z/p\Z$, but that to form $s$ it
is necessary to choose a minimal positive integer representative and
reinterpret it $\bmod (p-1)$.

\noindent
{\bf Verification.}
The signature is verified first that $1 \le r \le p-1$, or rejected.
The values
$$
v_1 = c^r r^s \bmod p, \hbox{ and } v_2 = a^m \bmod p,
$$
are next computed, and the equality $v_1 = v_2$ is verified or the
signature rejected.

\noindent{\bf Proof of equality.}
$v_1 = c^r a^{kl(m-xr)} = a^{xr} a^{m-xr} = a^m = v_2$.

%\begin{center}{\Large\bf MATH3024: Lecture 24}\end{center}

\section{Chaum's Blind Signature Scheme}

Chaum's blind signature scheme is an RSA-based scheme, adapted for
blind signatures.  In the protocol below we assume that Bob has set
up a public RSA key $(e,n)$ with corresponding private key $(d,n)$,
so that Bob's RSA signature functions is $S_B(m) = m^d$.

\begin{tabular}{*2{l@{}}}
1.
\begin{minipage}[t]{12.5cm}
{\it Initial setup:}
Alice obtains Bob's public key $(e,n)$ and chooses a random public
session key $k$, such that $0 < k < n$ and $\GCD(k,n) = 1$.
\end{minipage}\\
2. {\it Blinding:}
Alice computes $m^* = mk^e$, and sends $m^*$ to Bob.\\
3. {\it Signing:}
Bob computes $s^* = {m^*}^d$, which he sends back to Alice.\\
4. {\it Unblinding:}
Alice computes $s = k^{-1}s^*$, which equals $S_B(m) = m^d$.\\
\end{tabular}
\vspace{0.2cm}

As an application we mention a naive digital cash scheme.  Suppose
that Alice wants to withdraw a digital \$100 from her account to be
spent anonymously at a later date.  She writes $1000$ notes from the
bank, each certifying its value to be \$100, and blinds them, each
with a separate session key.  The bank asks for the session keys to
$999$ of these notes, verifies that each has the correct value, and
blindly signs the last one, deducting \$100 from her account, and
returns the blinded signed \$100 note to Alice for use as cash.

\section{Digital Cash Schemes}

We won't go into details of a particular digital cash protocol,
but list the ideal properties which such a scheme should satisfy,
as spelled out by Okomoto and Ohta in 1991 (Crypto'91).

1. Digital cash can be sent securely through an insecure channel.

2. Digital cash can not be copied or reused.

3. The spender remains anonymous under legitimate use of the protocol.

4. Spending does not require communication with a bank or external agency.

5. The cash is transferable.

6. The cash can be subdivided.

There are several proposed digital cash schemes, which provide both
partial and full solutions to these sets of conditions.  Okamoto and
Ohta provide a solution to all six of these conditions. Chaum has
proposed a variety of schemes which give partial solutions to
different subsets of the above, and Brands has a scheme which
satisfies the first four properties.  The complexity of the scheme
is largely dependent on the number of these properties which it
satisfies, so that the most complete scheme may not be the easiest
to describe or to implement.

We note that anonymity, property three of this list, relies on an
analogue blind signatures called restricted blind signatures, as in
the naive example above.  The naive example fails the above criteria,
for instance, failing to ensure against multiple spending.
